home *** CD-ROM | disk | FTP | other *** search
/ Hottest 6 / Hottest 6 (1996)(PDSoft)[!].iso / software / videoutils / h-m / mandelsquare / mandelsquare-1.06.lha / skip.c < prev    next >
C/C++ Source or Header  |  1992-10-12  |  13KB  |  538 lines
  1. /***************************************************************************
  2. *
  3. *  This contains routines to compress images one of two ways:
  4. *      1. Vertical Byte Run Length (VRUN)
  5. *      2. Vertical Byte Run Length With Skips (SKIP)
  6. *   from amiga/programs #274, dated jul 8 1987...
  7. *
  8. * The routines here compress a single bit-plane.  There's routines to
  9. * see how big the compressed result will be (xxxx_count_plane() )
  10. * and routines to actually compress the result into a buffer in memory
  11. * (xxxx_comp_plane() )  where xxxx is either vrun or skip depending....
  12. *
  13. *
  14. * VRUN compression format:
  15. *    a VRUN-compressed plane is a concatenation of VRUN-compressed columns.
  16. *    Each column is an op-count followed by a concatenation of op-count op's.
  17. *    An op is in one of these two formats:
  18. *        SAME_OP:  1-byte-count  followed by 1-byte to repeat count times.
  19. *        UNIQ_OP:  1-byte-count  followed by count bytes of data to copy
  20. *    The counts in either op must be 127 or less.  If it's a UNIQ_OP the
  21. *    hi bit of the count op is set (it's masked with 127 to find the actual
  22. *    count).
  23. *
  24. * SKIP compression format:
  25. *    a SKIP compressed plane is a concatenation of SKIP-compressed columns.
  26. *    Like a VRUN this is an op-count followed by a concatenation of op;s.
  27. *    However in this one we have 3 op formats:
  28. *       SKIP_OP:  Hi bit clear.  Count of bytes to skip.
  29. *       UNIQ_OP:  Hi bit set.  Remainder is count of data to copy. Data
  30. *                 follows immediately.
  31. *       SAME_OP:  A zero followed by a one-byte-count followed by one byte
  32. *                 of data to repeat count times.
  33. *
  34. ****************************************************************************
  35. *
  36. * Small changes made for SAS/C by Olaf `Olsen' Barthel: added registerized
  37. * parameters and STATIC declarations to make it easier for the compiler to
  38. * inline certain routines.
  39. *                          -olsen
  40. *
  41. ***************************************************************************/
  42.  
  43. #include <exec/types.h>
  44. #include <graphics/gfx.h>
  45.  
  46. #define MAXRUN 127
  47.  
  48. static WORD linebytes = 40;
  49. static WORD uniq_count;
  50. static unsigned char *uniq;
  51. static WORD op_count;
  52.  
  53. UBYTE * __regargs    skip_comp_plane(UBYTE *in, UBYTE *last_in, UBYTE *out, WORD next_line, WORD rows);
  54. WORD __regargs        skip_count_plane(UBYTE *in, UBYTE *last_in, WORD next_line, WORD rows);
  55.  
  56. STATIC WORD        vskip(unsigned char *in, unsigned char *last_in, WORD count);
  57. STATIC WORD        vsame(unsigned char *in, WORD count);
  58. STATIC WORD        skip_count_line(unsigned char *in, unsigned char *last_in, WORD count);
  59. STATIC unsigned char *    flush_uniq(unsigned char *stuff);
  60. STATIC int        copy_line_to_chars(unsigned char *in, unsigned char *out, int linebytes, int count);
  61. STATIC unsigned char *    skip_comp_line(unsigned char *in, unsigned char *last_in, unsigned char *out, WORD count);
  62. STATIC WORD        vrun_count_line(unsigned char *in, WORD count);
  63. STATIC WORD        vrun_count_plane(unsigned char *in, WORD next_line, WORD rows);
  64. STATIC unsigned char *    vrun_comp_line(unsigned char *in, unsigned char *out, WORD count);
  65. STATIC unsigned char *    vrun_comp_plane(unsigned char *in, unsigned char *out, WORD next_line, WORD rows);
  66.  
  67. /* count up how many in a column are the same between in and last_in ...
  68.    ie how big of a "skip" can we go on. */
  69.  
  70. STATIC WORD
  71. vskip(in, last_in, count)
  72.      register unsigned char *in;
  73.      register unsigned char *last_in;
  74.      register WORD count;
  75. {
  76.     register WORD skips;
  77.  
  78.     skips = 0;
  79.     while (--count >= 0)
  80.     {
  81.     if (*in != *last_in)
  82.         break;
  83.     in += linebytes;
  84.     last_in += linebytes;
  85.     skips++;
  86.     }
  87.     return (skips);
  88. }
  89.  
  90. /* vsame() - count up how many in a row (vertically) are the same as the
  91.    first one ... ie how big of a "same" op we can have */
  92. STATIC WORD
  93. vsame(in, count)
  94.      register unsigned char *in;
  95.      register WORD count;
  96. {
  97.     register unsigned char c;
  98.     register WORD same;
  99.  
  100.     c = *in;
  101.     in += linebytes;
  102.     --count;
  103.     same = 1;
  104.     while (--count >= 0)
  105.     {
  106.     if (*in != c)
  107.         break;
  108.     same++;
  109.     in += linebytes;
  110.     }
  111.     return (same);
  112. }
  113.  
  114.  
  115. /* skip_count_line() - figure out what size this column will compress
  116.    to using vertical-byte-run-length-with-skips encoding */
  117. STATIC WORD
  118. skip_count_line(in, last_in, count)
  119.      register unsigned char *in;
  120.      register unsigned char *last_in;
  121.      WORD count;
  122. {
  123.     WORD local_count;
  124.     WORD a_run;
  125.     WORD run_length;
  126.     WORD uniq_count = 0;
  127.     WORD comp_count = 1;    /* one for the op count */
  128.  
  129.  
  130.     if (vskip(in, last_in, count) == count)    /* skip whole column? */
  131.     return (1);
  132.     for (;;)
  133.     {
  134.     if (count <= 0)
  135.         break;
  136.     local_count = (count < MAXRUN ? count : MAXRUN);
  137.     a_run = 0;
  138.     if ((run_length = vskip(in, last_in, local_count)) > 1)
  139.     {
  140.         count -= run_length;
  141.         if (count > 0)    /* the last skip disappears */
  142.         comp_count += 1;
  143.         a_run = 1;
  144.     }
  145.     else if ((run_length = vsame(in, local_count)) > 3)
  146.     {
  147.         count -= run_length;
  148.         a_run = 1;
  149.         comp_count += 3;
  150.     }
  151.     if (a_run)
  152.     {
  153.         in += run_length * linebytes;
  154.         last_in += run_length * linebytes;
  155.         if (uniq_count > 0)
  156.         {
  157.         comp_count += uniq_count + 1;
  158.         uniq_count = 0;
  159.         }
  160.     }
  161.     else
  162.     {
  163.         in += linebytes;
  164.         last_in += linebytes;
  165.         uniq_count++;
  166.         count -= 1;
  167.         if (uniq_count == MAXRUN)
  168.         {
  169.         comp_count += uniq_count + 1;
  170.         uniq_count = 0;
  171.         }
  172.     }
  173.     }
  174. /*  if (count != 0)
  175.     {
  176.         printf("weird end count %d in skip_line_count\n");
  177.     }*/
  178.     if (uniq_count != 0)
  179.     {
  180.     comp_count += uniq_count + 1;
  181.     }
  182.     return (comp_count);
  183. }
  184.  
  185. /* skip_count_plane() - figure out what size this plane will compress
  186.    to using vertical-byte-run-length-with-skips encoding */
  187.  
  188. /*
  189. WORD
  190. skip_count_plane(in, last_in, next_line, rows)
  191.      unsigned char *in;
  192.      unsigned char *last_in;
  193.      WORD next_line;
  194.      WORD rows;
  195. */
  196.  
  197. WORD __regargs
  198. skip_count_plane(UBYTE *in, UBYTE *last_in, WORD next_line, WORD rows)
  199. {
  200.     WORD i;
  201.     WORD comp_count;
  202.  
  203.     linebytes = next_line;
  204.     comp_count = 0;
  205.     i = next_line;
  206.     while (--i >= 0)
  207.     {
  208.     comp_count += skip_count_line(in, last_in, rows);
  209.     in++;
  210.     last_in++;
  211.     }
  212.     return (comp_count);
  213. }
  214.  
  215. /* flush_uniq() - write out the "uniq" run that's been accumulating while
  216.    we've been looking for skips and "same" runs. */
  217. STATIC unsigned char *
  218. flush_uniq(stuff)
  219.      unsigned char *stuff;
  220. {
  221.     if (uniq_count > 0)
  222.     {
  223.     op_count++;
  224.     *stuff++ = (uniq_count | 0x80);
  225.     copy_line_to_chars(uniq, stuff, linebytes, uniq_count);
  226.     stuff += uniq_count;
  227.     uniq_count = 0;
  228.     }
  229.     return (stuff);
  230. }
  231.  
  232. STATIC int
  233. copy_line_to_chars(in, out, linebytes, count)
  234.      unsigned char *in, *out;
  235.      int linebytes, count;
  236. {
  237.     while (count--)
  238.     {
  239.     *out = *in;
  240.     out++;
  241.     in += linebytes;
  242.     }
  243.     return (0);
  244. }
  245.  
  246. /* skip_comp_line() - Compress "in" into "out" using vertical-byte-run-
  247.    with-skips encodeing. Return pointer to "out"'s next free space. */
  248.  
  249. STATIC unsigned char *
  250. skip_comp_line(in, last_in, out, count)
  251.      register unsigned char *in;
  252.      unsigned char *last_in;
  253.      unsigned char *out;
  254.      WORD count;
  255. {
  256.     register unsigned char *stuffit;
  257.     WORD local_count;
  258.     WORD a_run;
  259.     WORD run_length;
  260.  
  261. /* if can skip over whole column, then compact a bit by just setting the
  262.    "op count" for this column to zero */
  263.     if (vskip(in, last_in, count) == count)    /* skip whole column? */
  264.     {
  265.     *out++ = 0;
  266.     return (out);
  267.     }
  268.  
  269.     op_count = 0;        /* haven't done any op's yet */
  270.  
  271. /* initialize variables which keep track of how many uniq bytes we've gone
  272.    past, and where uniq run started. */
  273.     uniq_count = 0;
  274.     uniq = in;
  275.  
  276.     stuffit = out + 1;        /* skip past "op-count" slot in out array */
  277.     for (;;)
  278.     {
  279.     if (count <= 0)
  280.         break;
  281.     local_count = (count < MAXRUN ? count : MAXRUN);
  282.     a_run = 0;        /* first assume not a skip or a same run */
  283.     /* see how much could skip from here.  Two or more is worth skipping! */
  284.     if ((run_length = vskip(in, last_in, local_count)) > 1)
  285.     {
  286.         a_run = 1;
  287.         count -= run_length;
  288.         stuffit = flush_uniq(stuffit);    /* flush pending "uniq" run */
  289.         if (count > 0)    /* last skip vanishes */
  290.         {
  291.         op_count++;
  292.         *stuffit++ = run_length;
  293.         }
  294.     }
  295.     /* four or more of the same byte in a row compresses too */
  296.     else if ((run_length = vsame(in, local_count)) > 3)
  297.     {
  298.         a_run = 1;
  299.         count -= run_length;
  300.         op_count++;
  301.         stuffit = flush_uniq(stuffit);    /* flush pending "uniq" run */
  302.         *stuffit++ = 0;
  303.         *stuffit++ = run_length;
  304.         *stuffit++ = *in;
  305.     }
  306.     /* if it's a run of some sort update in and last_in pointer, and
  307.            reset the uniq pointer to the current position */
  308.     if (a_run)
  309.     {
  310.         in += run_length * linebytes;
  311.         last_in += run_length * linebytes;
  312.         uniq = in;
  313.         /* otherwise just continue accumulating stuff in uniq for later flushing
  314.            or immediate if it get's past MAXRUN */
  315.     }
  316.     else
  317.     {
  318.         in += linebytes;
  319.         last_in += linebytes;
  320.         uniq_count++;
  321.         count -= 1;
  322.         if (uniq_count == MAXRUN)
  323.         {
  324.         stuffit = flush_uniq(stuffit);
  325.         uniq = in;
  326.         }
  327.     }
  328.     }
  329. /* if came to end of column within a uniq-run still have to flush it */
  330.     if (uniq_count != 0)
  331.     {
  332.     stuffit = flush_uniq(stuffit);
  333.     }
  334. /*  if (count != 0)
  335.     {
  336.         printf("weird end count %d in skip_line_count\n", count);
  337.     }*/
  338. /* and stuff the first byte of this (compressed) column with the op_count */
  339.     *out = op_count;
  340.     return (stuffit);
  341. }
  342.  
  343. /* skip_comp_plane() - Compress "in" into "out" using vertical-byte-run-
  344.    with-skips encodeing. Return pointer to "out"'s next free space. */
  345.  
  346. /*
  347. unsigned char *
  348. skip_comp_plane(in, last_in, out, next_line, rows)
  349.      unsigned char *in;
  350.      unsigned char *last_in;
  351.      unsigned char *out;
  352.      WORD next_line;
  353.      WORD rows;
  354. */
  355.  
  356.  
  357. UBYTE * __regargs
  358. skip_comp_plane(UBYTE *in, UBYTE *last_in, UBYTE *out, WORD next_line, WORD rows)
  359. {
  360.     WORD i;
  361.  
  362.     linebytes = next_line;
  363.     i = next_line;
  364.     while (--i >= 0)
  365.     {
  366.     out = skip_comp_line(in, last_in, out, rows);
  367.     in++;
  368.     last_in++;
  369.     }
  370.     return (out);
  371. }
  372.  
  373. /* vrun_count_line() - figure out what size this column will compress
  374.    to using vertical-byte-run-length encoding */
  375.  
  376. STATIC WORD
  377. vrun_count_line(in, count)
  378.      register unsigned char *in;
  379.      WORD count;
  380. {
  381.     WORD local_count;
  382.     WORD a_run;
  383.     WORD run_length;
  384.     WORD uniq_count = 0;
  385.     WORD comp_count = 1;    /* one for the op count */
  386.  
  387.  
  388.     for (;;)
  389.     {
  390.     if (count <= 0)
  391.         break;
  392.     local_count = (count < MAXRUN ? count : MAXRUN);
  393.     a_run = 0;
  394.     if ((run_length = vsame(in, local_count)) > 2)
  395.     {
  396.         a_run = 1;
  397.         comp_count += 2;
  398.     }
  399.     if (a_run)
  400.     {
  401.         in += run_length * linebytes;
  402.         count -= run_length;
  403.         if (uniq_count > 0)
  404.         {
  405.         comp_count += uniq_count + 1;
  406.         uniq_count = 0;
  407.         }
  408.     }
  409.     else
  410.     {
  411.         in += linebytes;
  412.         uniq_count++;
  413.         count -= 1;
  414.         if (uniq_count == MAXRUN)
  415.         {
  416.         comp_count += uniq_count + 1;
  417.         uniq_count = 0;
  418.         }
  419.     }
  420.     }
  421. /*  if (count != 0)
  422.     {
  423.         printf("weird end count %d in vrun_line_count\n");
  424.     }*/
  425.     if (uniq_count != 0)
  426.     {
  427.     comp_count += uniq_count + 1;
  428.     }
  429.     return (comp_count);
  430. }
  431.  
  432. /* vrun_count_plane() - figure out what size this plane will compress
  433.    to using vertical-byte-run-length encoding */
  434. STATIC WORD
  435. vrun_count_plane(in, next_line, rows)
  436.      unsigned char *in;
  437.      WORD next_line;
  438.      WORD rows;
  439. {
  440.     WORD i;
  441.     WORD comp_count;
  442.  
  443.     linebytes = next_line;
  444.     comp_count = 0;
  445.     i = next_line;
  446.     while (--i >= 0)
  447.     {
  448.     comp_count += vrun_count_line(in, rows);
  449.     in++;
  450.     }
  451.     return (comp_count);
  452. }
  453.  
  454.  
  455. /* vrun_comp_line() - Compress "in" into "out" using vertical-byte-run
  456.    encodeing. Return pointer to "out"'s next free space. */
  457.  
  458. STATIC unsigned char *
  459. vrun_comp_line(in, out, count)
  460.      register unsigned char *in;
  461.      unsigned char *out;
  462.      WORD count;
  463. {
  464.     register unsigned char *stuffit;
  465.     WORD local_count;
  466.     WORD a_run;
  467.     WORD run_length;
  468.  
  469.     uniq_count = op_count = 0;
  470.     uniq = in;
  471.  
  472.     stuffit = out + 1;
  473.     for (;;)
  474.     {
  475.     if (count <= 0)
  476.         break;
  477.     local_count = (count < MAXRUN ? count : MAXRUN);
  478.     a_run = 0;
  479.     if ((run_length = vsame(in, local_count)) > 2)
  480.     {
  481.         a_run = 1;
  482.         stuffit = flush_uniq(stuffit);
  483.         *stuffit++ = run_length;
  484.         *stuffit++ = *in;
  485.     }
  486.     if (a_run)
  487.     {
  488.         op_count++;
  489.         in += run_length * linebytes;
  490.         count -= run_length;
  491.         uniq = in;
  492.     }
  493.     else
  494.     {
  495.         in += linebytes;
  496.         uniq_count++;
  497.         count -= 1;
  498.         if (uniq_count == MAXRUN)
  499.         {
  500.         stuffit = flush_uniq(stuffit);
  501.         uniq = in;
  502.         }
  503.     }
  504.     }
  505.     if (uniq_count != 0)
  506.     {
  507.     stuffit = flush_uniq(stuffit);
  508.     }
  509. /*  if (count != 0)
  510.     {
  511.         printf("weird end count %d in vrun_line_count\n", count);
  512.     }*/
  513.     *out = op_count;
  514.     return (stuffit);
  515. }
  516.  
  517. /* vrun_comp_plane() - Compress "in" into "out" using vertical-byte-run
  518.    encodeing. Return pointer to "out"'s next free space. */
  519.  
  520. STATIC unsigned char *
  521. vrun_comp_plane(in, out, next_line, rows)
  522.      unsigned char *in;
  523.      unsigned char *out;
  524.      WORD next_line;
  525.      WORD rows;
  526. {
  527.     WORD i;
  528.  
  529.     linebytes = next_line;
  530.     i = next_line;
  531.     while (--i >= 0)
  532.     {
  533.     out = vrun_comp_line(in, out, rows);
  534.     in++;
  535.     }
  536.     return (out);
  537. }
  538.